package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/29 8:56
 * @description :6道
 * 别停留等待。
 * persevere to last
 * 2021.10.29
 */
public class t20211029 {


    //209 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int minLne = Integer.MAX_VALUE;
        int flag = 0;

        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= target) {
                minLne = Math.min(minLne, 1);
                flag++;
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {

                sum = sum + nums[j];
                if (sum >= target) {
                    minLne = Math.min(minLne, j - i + 1);
                    flag++;
                    break;
                }


            }


        }
        return flag != 0 ? minLne : 0;
    }

    //滑动窗口
    static public int minSubArrayLen2(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int arr_len = nums.length;

        int end = 0, start = 0, flag = 0;

        int sum = 0, min_len = Integer.MAX_VALUE;

        while (end < arr_len) {

            sum = sum + nums[end];
            while (sum >= target) {
                min_len = Math.min(min_len, end - start + 1);
                sum -= nums[start];
                start++;
                flag++;
            }

            end++;

        }

        return flag == 0 ? 0 : min_len;//判断min_Len是否进过修改，若没有，则说明数组中所有元素加起来都小于target
    }

    //判断是否为2的幂
    static public boolean isTwoMin(int n) {
        if (n <= 0) {
            return false;
        }

        String[][] arr = {
                {"1", "2", "4", "8"},
                {"16", "32", "64"},
                {"128", "256", "512"},
                {"1024", "2048", "4096"}
        };

        String num = n + "";
        int len = num.length();

        for (int i = 0; i < arr[len - 1].length; i++) {
            if (num.equals(arr[len - 1][i])) {
                return true;
            }
        }

        return false;

    }

    static public boolean isTwoMin2(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }

    //335.路径交叉
    public boolean isSelfCrossing(int[] distance) {
        if (distance == null || distance.length < 4) {
            return false;
        }


        for (int i = 3; i < distance.length; i++) {
            if (distance[i - 3] >= distance[i - 1] && distance[i - 2] <= distance[i]) {
                return true;
            }
            if (i >= 4 && distance[i - 3] == distance[i - 1] && distance[i] >= distance[i - 2] - distance[i - 4]) {
                return true;
            }
            if (i >= 5 && distance[i - 1] <= distance[i - 3] && distance[i - 2] > distance[i - 4] && distance[i] + distance[i - 4] >= distance[i - 2] && distance[i - 1] + distance[i - 5] >= distance[i - 3])
                return true;


        }

        return false;

    }

    //200.岛屿数量
    public int numIslands(char[][] grid) {
        if (grid == null) return 0;

        int rows = grid.length, columns = grid[0].length;
        int num = 0;


        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == 49) {
                    dfs(grid, i, j, rows, columns);
                    num++;
                }
            }
        }

        return num;
    }

    /**
     * @return void
     * @Author 李红磊
     * @Description //TODO
     * @Date 2021/10/29 15:35
     * @param: grid 目标矩阵
     * @param: x 坐标
     * @param: y 坐标
     * @param: rows 行数
     * @param: columns 列数
     **/
    private void dfs(char[][] grid, int x, int y, int rows, int columns) {
        if (x < 0 || x > rows - 1 || y < 0 || y > columns - 1 || grid[x][y] != 49) {
            //表示坐标不合法或者已经访问过
            return;
        }


        grid[x][y] = 97;

        //进行上下左右四个方向的遍历
        dfs(grid, x - 1, y, rows, columns);
        dfs(grid, x + 1, y, rows, columns);
        dfs(grid, x, y - 1, rows, columns);
        dfs(grid, x, y + 1, rows, columns);

        return;
    }

    //547.省份数量
    public int findCircleNum(int[][] isConnected) {

        UnionFind unionFind = new UnionFind();

        for (int i = 0; i < isConnected.length; i++) {
            unionFind.add(i);
            for (int j = 0; j < isConnected[0].length; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.merge(i, j);
                }
            }
        }
        return unionFind.getNumOfSets();
    }


    //面试题08.07 无重复字符串的排列组合
    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        boolean[] visit = new boolean[chars.length];
        ArrayList<String> res = new ArrayList<>();

        List<String> list = strDfs(chars, visit, "", res);

        return list.toArray(new String[chars.length]);
    }

    /**
     * @return void
     * @Author 李红磊
     * @Description //TODO
     * @Date 2021/10/29 20:28
     * @param: chars 目标字符串的字符数组
     * @param: visit 用于记录已经访问的
     * @param: cur 当前路径
     * @param: res 用于返回的集合
     **/
    private ArrayList<String> strDfs(char[] chars, boolean[] visit, String cur, ArrayList<String> res) {
        if (cur.length() == chars.length) {
            res.add(cur);
            return res;
        }

        for (int i = 0; i < chars.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                res = strDfs(chars, visit, cur + chars[i], res);
                visit[i] = false;
            }
        }
        return res;
    }


    public static void main(String[] args) {
        t20211029 t20211029 = new t20211029();
        char[][] test_arr = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };


        String str = "qwe";
        char[] chars = str.toCharArray();


        String[] strings = t20211029.permutation(str);
        Arrays.stream(strings)
                .forEach(s -> System.out.println(s));

    }


}

//并查集
class UnionFind {

    Map father = new HashMap<Integer, Integer>();//记录父节点

    private int numOfSets = 0;// 记录集合的数量


    public void add(int x) {
        if (!father.containsKey(x)) {
            father.put(x, null);
            numOfSets++;
        }
    }

    //合并
    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {//表面两个元素的标志不同
            father.put(rootX, rootY);
            numOfSets--;
        }

    }

    //查找标志量
    private int find(int item) {
        int root = item;

        while (father.get(root) != null) {
            root = (int) father.get(root);
        }

        while (item != root) {
            int original_father = (int) father.get(item);
            father.put(item, root);
            item = original_father;

        }


        return root;
    }

    public int getNumOfSets() {
        return numOfSets;
    }

    //判断两个元素是否为一个集合（就是判断两者的标志量是否相等）
    public boolean isConnection(int x, int y) {
        return find(x) == find(y);
    }


}
